package temp.leetcode.editor.cn;

//给你一个二进制字符串数组 strs 和两个整数 m 和 n 。
//
//
// 请你找出并返回 strs 的最大子集的长度，该子集中 最多 有 m 个 0 和 n 个 1 。
//
//
// 如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的 子集 。
//
//
//
// 示例 1：
//
//
//输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
//输出：4
//解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
//其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于
//n 的值 3 。
//
//
// 示例 2：
//
//
//输入：strs = ["10", "0", "1"], m = 1, n = 1
//输出：2
//解释：最大的子集是 {"0", "1"} ，所以答案是 2 。
//
//
//
//
// 提示：
//
//
// 1 <= strs.length <= 600
// 1 <= strs[i].length <= 100
// strs[i] 仅由 '0' 和 '1' 组成
// 1 <= m, n <= 100
//
//
// Related Topics 数组 字符串 动态规划 👍 930 👎 0

/**
 * 一和零
 *
 * @author saint
 */
class P474_OnesAndZeroes{
    public static void main(String[] args) {
        Solution solution = new P474_OnesAndZeroes().new Solution();
        solution.findMaxForm(new String[]{"10","0","1"},1,1);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
//        //使用三维数组dp[i][j][k]，表示0-i下标的字符串，0的数量小于j,1的数量小于k的子集元素个数
//        int[][][] dp= new int[strs.length][m+1][n+1];
        int[][] traStrings = new int[strs.length][2];
        for (int i = 0; i < strs.length; i++) {
            int[] traString = calString(strs[i]);
            traStrings[i] = traString;
        }
//        //初始化
//        for (int i = traStrings[0][0]; i < m + 1; i++) {
//            for (int j = traStrings[0][1]; j < n + 1; j++) {
//                dp[0][i][j] = 1;
//            }
//        }
//        //遍历
//        for (int i = 1; i < strs.length; i++) {
//            for (int j = 0; j < m+1  ; j++) {
//                for (int k = 0; k <n+1 ; k++) {
//                    if (j<traStrings[i][0]||k<traStrings[i][1]){
//                        dp[i][j][k] = dp[i-1][j][k];
//                    }else {
//                        dp[i][j][k] = Math.max(dp[i-1][j][k],dp[i-1][j-traStrings[i][0]][k-traStrings[i][1]]+1);
//                    }
//                }
//            }
//        }
        //使用滚动数组dp[i][j]表示不超过i个0和j个1的子集元素个数
        int[][] dp = new int[m+1][n+1];
        for (int i = 0; i < strs.length; i++) {
            for(int j = m;j>=traStrings[i][0];j--){
                for (int k = n;k>=traStrings[i][1];k--){
                    dp[j][k] = Math.max(dp[j][k],dp[j-traStrings[i][0]][k-traStrings[i][1]]+1);
                }
            }
        }
        return dp[m][n];
    }

    //计算字符串0和1个数
    public int[] calString(String s){
        int[] res = new int[2];
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i)=='0'){
                res[0]++;
            }else{
                res[1]++;
            }
        }
        return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
